package com.study.dataStructure.searchAlgorithms;

import com.study.dataStructure.exception.FibonacciArrSizeException;
import com.study.dataStructure.util.ArraysUtil;

import java.io.FileOutputStream;
import java.io.FileWriter;
import java.util.Properties;

/**
 * @author tiny
 * @date 2021/11/8 23:12
 * @Description: 斐波那契查找
 */
public class FibonacciSearch {

    public static void main(String[] args) {

//        boolean b = ArraysUtil.serializeRandomArr(25, 100, "./arr.properties");

        int[] arr = ArraysUtil.antiSerializationArr("arr", "./arr.properties");

        int[] fbncArr = createFibonacciArr2(arr.length);
        int index = search(arr, fbncArr, 77);
        if(index>-1){
            System.out.println("索引位置为: "+index);
            System.out.println("arr["+index+"] = "+arr[index]);
        }else{
            System.out.println("数组中未查询到!");
        }

    }

    /**
     * 生成指定长度的斐波那契数组
     * @param size
     * @return
     */
    private static int[] createFibonacciArr(int size){
        if(size<=2) throw new FibonacciArrSizeException();
        int[] arr = new int[size];
        arr[0] = 1;
        arr[1] = 1;
        int i = 2;
        while(i<size){
//            arr[i++] = arr[i-2] + arr[i-1]; //错误
            arr[i] = arr[i-2] + arr[i-1];
            i++;
        }
        return arr;
    }

    /**
     * 根据待查找数组的长度生成适用长度的斐波那契数组
     * @param checkLenght 待查找数组的长度
     * @return
     */
    private static int[] createFibonacciArr2(int checkLenght){
        int[] arr = new int[]{1,1};

        for (int nextNum = arr[0] + arr[1]; true; nextNum=arr[arr.length-1] + arr[arr.length-2] ) {
            int[] newArr = new int[arr.length + 1];
            ArraysUtil.copyArray(arr,newArr);
            newArr[newArr.length-1] = nextNum;
            arr = newArr;
            if(nextNum>=checkLenght) break;
        }
        return arr;
    }

    public static int search(int[] arr , int[] fibonacciArr, int key){
        //原数组末位索引
        int n = arr.length-1;
        //将原数组补齐
        int[] newArr = new int[fibonacciArr[fibonacciArr.length - 1]];
        ArraysUtil.copyArray(arr,newArr);
        for (int i = arr.length; i < newArr.length; i++) {
            newArr[i] = arr[n];
        }

        System.out.println(ArraysUtil.toString(newArr));

        int left = 0;
        int right = newArr.length-1;
        int k = fibonacciArr.length-1;
        while(left<=right){
            int mid = left + fibonacciArr[k-1] - 1;
            if(newArr[mid] == key) {
                return mid>n ? n : mid;
            }else if(newArr[mid] < key){
                left = mid+1;
                // 第二轮 f[k-2]个元素中,分成左f[k-3],右f[k-4]
                k = k-2;
            }else{
                right = mid;
                // 第二轮 f[k-1]个元素中,分成左f[k-2],右f[k-3]
                k = k-1;
            }
        }
        return -1;
    }

}
